﻿/*
Spiral Matrix Total Accepted: 28957 Total Submissions: 139437 My Submissions Question Solution
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

*/
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
//#include <cstdio>

using namespace std;



class Solution1 {

public:
	int maxSubArray(vector<int>& nums) {

		int maxinum = 0;
		int sum = 0;

		for (size_t i = 0; i < nums.size(); i++)
		{
			for (size_t j = i; j < nums.size(); j++)
			{
				for (size_t k = i; k <= j; k++)
				{
					sum += nums[k];
				}
				if (sum > maxinum)
				{
					maxinum = sum;
				}
				sum = 0;
			}

		}
		return maxinum;

	}
};


class Solution2 {
	/*DP*/
public:
	int maxSubArray(vector<int>& nums) {

		int size = nums.size();
		vector<int> all(size, 0);
		vector<int> start(size, 0);

		start[size - 1] = nums[size - 1];
		all[size - 1] = nums[size - 1];

		for (int i = size - 2; i >= 0; i--)
		{
			start[i] = max(nums[i], nums[i] + start[i + 1]);
			all[i] = max(start[i], all[i + 1]);
		}
		return all[0];
	}
};


class Solution3 {
	/*DP*/
public:
	int maxSubArray(vector<int>& nums) {

		int size = nums.size();
		int start;
		int all;
		start = nums[size - 1];
		all = nums[size - 1];

		for (int i = size - 2; i >= 0; i--)
		{
			start = max(nums[i], nums[i] + start);
			all = max(start, all);
		}
		return all;
	}
};

class Solution {
public:
	vector<int> spiralOrder(vector<vector<int> > &matrix) {
		vector<int> result;

		if (matrix.empty())
			return result;

		int beginX = 0, endX = matrix[0].size() - 1;
		int beginY = 0, endY = matrix.size() - 1;
		while (true)
		{
			//From left to right
			for (int i = beginX; i <= endX; ++i)
				result.push_back(matrix[beginY][i]);
			if (++beginY > endY)break;

			//from top down
			for (int i = beginY; i <= endY; ++i)
				result.push_back(matrix[i][endX]);
			if (beginX > --endX)break;


			//from right to left
			for (int i = endX; i >= beginX; --i)
				result.push_back(matrix[endY][i]);
			if (beginY > --endY)break;

			//from down to top
			for (int i = endY; i >= beginY; --i)
				result.push_back(matrix[i][beginX]);
			if (++beginX > endX)break;
		}

		return result;

	}
};


int main(int argc, char* argv[])
{
	cout << "Max Subarray" << endl;

	cout << "Input n" << endl;


	int n;
	vector<int> nums;
	freopen("testData.txt", "r", stdin);
	while (cin >> n)
	{
		cout << n << endl;
		nums.push_back(n);


	}

	int sum;
	Solution s;
	sum = s.maxSubArray(nums);
	cout << "The sum of subarray" << sum << endl;

	system("pause");


	/*
	while(n)
	{
	int i;
	cin>>i;
	nums.push_back(i);
	n--;
	}

	cout<<"Input nums"<<endl;

	for(int i = 0; i < nums.size();i++)
	{
	cout<<nums[i]<<" ";
	}
	cout<<endl;

	Solution s;
	*/
	//result = s.pow(x,n);

	//cout<<"The result of ("<<x<<","<<n<<") is : " <<result<<endl;

	//fclose(stdin);

	return 0;
}